The present invention relates generally to improved methods and apparatus for protecting digital information from copying, and more particularly to electronic techniques for watermarking maps and other structured data.
With the widespread availability of digital information and the ease of copying such information, the problem of protecting that information from illicit copying has gained new prominence. A widely used method for addressing this problem is watermarking. This technique is also called fingerprinting and involves embedding hidden information into the data which encodes ownership and copyright information. Data suspected of being pirated can then be tested for this hidden information, determining if the data is copyrighted. Furthermore, by embedding unique hidden information into each copy, pirated data can be traced back to its original purchaser.
This approach has been applied to a wide range of media, such as images, audio, video, and the like. More recently, intellectual property protection problems related to VLSI design, such as placement and routing design data and implementations of finite state machines, have also been addressed in this fashion. In addition, there are cryptographic protocols which address related issues, such as how to distribute copies with guarantees of anonymity and reliable authentication.
The present invention addresses the application of watermarking techniques to protect map and other structured data. Consider the following situation, by way of example. Through expensive surveys, a company, referred to as the owner of the map, compiles accurate map data, represented by a weighted graph where nodes represent locations, edges represent links between locations, and the weights represent the distance between adjacent locations. This data is then sold to other parties called providers who provide end users access to it. This access is generally indirect in the sense that the provider allows the end users to query pairs of nodes, such as a starting point like New York City and an ending point like Chicago. The provider then responds to each query with appropriate information related to the pair, such as the distance between the nodes, or a shortest route, or both. This situation already exists for maps of the US roadway system, with companies such as MapQuest acting as map owners, web sites like Yahoo! acting as providers, and end users across the Internet accessing the data. In such a context, protecting the underlying data presents a variety of problems. For example, a watermark cannot distort the underlying data in a way that eliminates the value of the map, or which is easily detectable and countered. In addition, it is not hard to envision similar situations or data structures for which these problems could arise, such as providing routing information on a network.
A more complete understanding of the present invention, as well as further features and advantages of the invention, will be apparent from the following Detailed Description and the accompanying drawings.